struct Trie{
    string word;
    unordered_map<char,Trie*> next;
    
    Trie(){
        word = "";
    }
};
void insert(Trie* root,const string& s){
    Trie* node = root;
    for(auto e : s){
        if(!node->next.count(e)){
            node->next[e] = new Trie();
        }        
        node = node->next[e];
    }
    node->word = s; 
}


class Solution {
public:
    int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
    
    bool dfs(vector<vector<char>>& board,int x,int y,set<string>& ret,Trie* cur){
        char e = board[x][y];
        if(!cur->next.count(e)){
            return false;
        }
    
        cur = cur->next[e];
        if(cur->word.size() > 0){
            ret.insert(cur->word);
        }
        
        board[x][y] = '#';
        for(int i = 0;i < 4;i++){
            int xx = x + dir[i][0];
            int yy = y + dir[i][1];
            if(xx >= 0 && xx < board.size() && yy >= 0 && yy < board[0].size()){
                if(board[xx][yy] != '#'){
                    dfs(board,xx,yy,ret,cur);
                }
            }
        }
        board[x][y] = e;
        return true;
    }
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        set<string> ret;
        Trie* root = new Trie();
        vector<string> ans;

        
        for(auto& s : words){
            insert(root,s);
        }
        
        for(int i = 0;i < board.size();i++){
            for(int j = 0;j < board[0].size();j++){
                
                dfs(board,i,j,ret,root);
            }
        }
        
        for (auto & word: ret) {
            ans.emplace_back(word);
        }
     
        return ans;
    }
};
